<?php
/**
 * Created by PhpStorm.
 * User: lili
 * Date: 19-3-23
 * Time: 下午2:22
 */

require_once "../tools/tools.php";


if('cli'!==PHP_SAPI){
    echo "必须使用cli";
    exit();
}

echo "假设把只包含质因子2、3和5的数称作丑数（Ugly Number）。
例如6、8都是丑数，但14不是，因为它包含质因子7。 
习惯上我们把1当做是第一个丑数。求按从小到大的顺序排列的前n个丑数（以数组的形式返回）\n";



fwrite(STDOUT,"输入n:");
$n = trim(fgets(STDIN));


/**
 *
 * 每次我们的丑数都是前面的丑数乘以 2或者3或者5 生成
 * 每次我们把数组里面的丑数 *2 *3 *5分别放进 三个队列里面
 * 当然我们可以可以使用极好来模拟队列，不需要真的生成队列
 * 至于不同队列重复的数字，由于从小到大排序，我们在插入的时候，相同的必然都在队列头
 * 一起排出就行
 * 我参考 https://blog.csdn.net/Fly_as_tadpole/article/details/82705774
 *
 * @param [int] $n 输出前面n个丑数
 * @return array
 *
 * **/

function GetUglyNumber_Solution($n)
{
    $arr = [1];

    $p1=0;$p2=0;$p3=0;//队列的指针位置

    while (count($arr)<$n){
        $newnum = min($arr[$p1]*2,$arr[$p2]*3,$arr[$p3]*5);//三个队列的最小

        if($arr[$p1]*2==$newnum){
            $p1++;
        }
        if($arr[$p2]*3==$newnum){
            $p2++;
        }
        if($arr[$p3]*5==$newnum){
            $p3++;
        }

        $arr[]=$newnum;

    }
    return $arr;

}


$time_start = microtime_float();


echo  "丑数从小到大排列". ( implode(',',GetUglyNumber_Solution($n))       )."\n" ;

$time_end = microtime_float();
$time = $time_end - $time_start;

echo "Did nothing in $time seconds\n";

